package com.sailing.core.java.util;

import java.util.Iterator;
import java.util.Map;


public class TreeMap<K,V> {
	public static void main(String[] args) {
		TreeMap treeMap = new TreeMap<String, String>();
		
	}
	 /**
     * Recursive "helper method" that does the real work of the
     * previous method.  Identically named parameters have
     * identical definitions.  Additional parameters are documented below.
     * It is assumed that the comparator and size fields of the TreeMap are
     * already set prior to calling this method.  (It ignores both fields.)
     *
     * @param level 树的高度. 初始调用为 0.
     * @param lo 子树的第一个节点序号. Initial should be 0.
     * @param hi 子树的最后一个节点序号.  Initial should be  总数减一（size-1）.
     * @param redLevel the level at which nodes should be red.
     *        Must be equal to computeRedLevel for tree of this size.
     */
    public final Entry<K,V> buildFromSorted(int level, int lo, int hi,
					     int redLevel,
					     Iterator it,
					     java.io.ObjectInputStream str,
					     V defaultVal)
        throws  java.io.IOException, ClassNotFoundException {
        /*
         * Strategy: The root is the middlemost element. To get to it, we
         * have to first recursively construct the entire left subtree,
         * so as to grab all of its elements. We can then proceed with right
         * subtree.
         *
         * The lo and hi arguments are the minimum and maximum
         * indices to pull out of the iterator or stream for current subtree.
         * They are not actually indexed, we just proceed sequentially,
         * ensuring that items are extracted in corresponding order.
         */

        if (hi < lo) return null;

        int mid = (lo + hi) / 2;

        Entry<K,V> left  = null;
        if (lo < mid)
            left = buildFromSorted(level+1, lo, mid - 1, redLevel,
				   it, str, defaultVal);

        // extract key and/or value from iterator or stream
        K key;
        V value;
        if (it != null) {
            if (defaultVal==null) {
                Map.Entry<K,V> entry = (Map.Entry<K,V>)it.next();
                key = entry.getKey();
                value = entry.getValue();
            } else {
                key = (K)it.next();
                value = defaultVal;
            }
        } else { // use stream
            key = (K) str.readObject();
            value = (defaultVal != null ? defaultVal : (V) str.readObject());
        }

        Entry<K,V> middle =  new Entry<K,V>(key, value, null);

        // color nodes in non-full bottommost level red
        if (level == redLevel)
            middle.color = RED;

        if (left != null) {
            middle.left = left;
            left.parent = middle;
        }

        if (mid < hi) {
            Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
					       it, str, defaultVal);
            middle.right = right;
            right.parent = middle;
        }

        return middle;
    }
    /**
     * Test two values for equality.  Differs from o1.equals(o2) only in
     * that it copes with <tt>null</tt> o1 properly.
     */
    final static boolean valEquals(Object o1, Object o2) {
        return (o1==null ? o2==null : o1.equals(o2));
    }
    private static final boolean RED   = false;
    private static final boolean BLACK = true;
    static final class Entry<K,V> implements Map.Entry<K,V> {
    	K key;
            V value;
            Entry<K,V> left = null;
            Entry<K,V> right = null;
            Entry<K,V> parent;
            boolean color = BLACK;

            /**
             * Make a new cell with given key, value, and parent, and with
             * <tt>null</tt> child links, and BLACK color.
             */
            Entry(K key, V value, Entry<K,V> parent) {
                this.key = key;
                this.value = value;
                this.parent = parent;
            }

            /**
             * Returns the key.
             *
             * @return the key
             */
            public K getKey() {
                return key;
            }

            /**
             * Returns the value associated with the key.
             *
             * @return the value associated with the key
             */
            public V getValue() {
                return value;
            }

            /**
             * Replaces the value currently associated with the key with the given
             * value.
             *
             * @return the value associated with the key before this method was
             *         called
             */
            public V setValue(V value) {
                V oldValue = this.value;
                this.value = value;
                return oldValue;
            }

            public boolean equals(Object o) {
                if (!(o instanceof Map.Entry))
                    return false;
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;

                return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
            }

            public int hashCode() {
                int keyHash = (key==null ? 0 : key.hashCode());
                int valueHash = (value==null ? 0 : value.hashCode());
                return keyHash ^ valueHash;
            }

            public String toString() {
                return key + "=" + value;
            }
        }

}
